Relational database management systems typically utilize one of two space allocation techniques for data stored in database tables—physical allocation or logical allocation. In many database systems that utilize physical space allocation techniques, space is allocated in fixed-size chunks (often referred to as extents). After a fixed-size chunk of space has been allocated and data have been written to the allocated space, deleting portions of the data from the space does not automatically deallocate the space occupied by the deleted data. Consequently, deleting portions of the data does not make the space available to store other data. Instead, a reorganization operation must be performed to regain the free space occupied by the deleted data and to “clean up” the space. A reorganization operation generally must be planned and initiated by a database administrator, adding to the total cost of ownership for database systems that utilize physical space allocation techniques.
One of the primary advantages to using a logical space allocation technique is that reorganization operations are not necessary to reclaim previously allocated, unused space. For instance, with database systems that utilize logical space allocation techniques, such as the MaxDB database system available from SAP® AG, space is allocated in uniformly-sized units referred to as pages—typically with a page size in the range of 4 kilobytes to 64 kilobytes. After a page has been allocated and data have been written to the page, deleting all data in the page will automatically free the space occupied by the page, making the space available to store other data. It is not necessary to have an administrator perform a reorganization operation to manually reclaim the unused space. Consequently, when compared with database systems that use physical space allocation techniques, database systems that utilize logical space allocation techniques tend to require less administration and therefore have a lower total cost of ownership.
Database systems that implement logical space allocation techniques often utilize what is commonly referred to as a “converter” (sometimes referred to as a “converter page map” or “page converter”) for mapping (e.g., converting) logical page addresses to physical page addresses. For instance, when an application initiates a write operation to write to an existing page, the write operation will specify a logical page address. A database system processing the write operation will refer to a converter map (e.g., a table), managed by the converter, to identify the physical page address associated with the logical page address referenced in the write operation. To avoid frequently and unnecessarily accessing secondary storage (e.g., magnetic or optical fixed-disks), database systems implement a data cache in memory for processing input/output operations. The converter map that maps logical page addresses to physical page addresses will typically occupy a portion of the data cache.
In addition to a converter, database systems that implement logical space allocation techniques often utilize a technique referred to as “shadow paging.” Shadow paging is a copy-on-write technique for avoiding in-place updates of pages. For example, with shadow paging, when an application modifies an existing allocated page (e.g., by initiating a write operation to write data to the existing page), a new copy of the existing page is generated and assigned or mapped to the logical page. Accordingly, after a write operation to an existing page, the logical page associated with the existing page will be mapped to two different versions of the page—an old version (referred to as the “shadow page”), representing the state of the data prior to processing the write operation, and a new version, representing the state of the data after processing the write operation. The logical page is marked as “dirty” to indicate that the logical page is modified. Periodically, those logical pages marked as dirty are flushed (e.g., written from the data cache to secondary storage). After the old copy of the page—that is, the shadow copy of the logical page—is not needed anymore (e.g., after performing a savepoint operation), the old physical page is reclaimed by a free block manager, so it can be reused for new data.
With database systems that utilize shadow paging techniques, due to the converter (e.g., the converter map), which maps logical pages to physical pages, there is a memory overhead associated with the logical space allocation scheme described above. In general, the size of the converter map, and thus the amount of memory dedicated for the converter map, is directly dependent upon the overall size of the database. As an example, given a typical page size and converter structure in an existing database system, the memory overhead may be approximately one tenth of one percent (0.1%) of the total data volume of secondary storage (e.g., disks or solid state drives). Accordingly, for each one terabyte (1 TB) of data volume in secondary storage, there will be permanent memory overhead for the converter map of about one gigabyte (1 GB). As the converter map must be read into memory upon start up, the larger the converter map, the longer it will take the database system to initialize on start up. Nonetheless, given the size of a typical database (e.g., less than one terabyte (1 TB) in size), the size of the converter map is manageable.
In certain scenarios, for example, where a database is utilized to process and store hundreds of Terabytes of data, the corresponding size of the converter map becomes prohibitively large. For example, given the size ratio expressed above, a one hundred Terabyte (100 TB) database will require one hundred Gigabytes (100 GB) of memory—a prohibitively large requirement even for high-end systems. The large size requirement for the converter map is prohibitive both on the basis of the cost of memory, as well as the time it would take for the converter map to be read into memory on start up. Consequently, there is a desire and need for an alternative space allocation technique for use with database systems that use logical space allocation and shadow paging techniques for storing extremely large amounts of data.